Applications of logic programming and discrete optimization are often formulated as Constraint Satisfaction Problems. A Constraint Satisfaction Problem typically requires that an arbitrary set of constraints be satisfied. A search procedure is employed to enumerate all problem solutions that simultaneously satisfy all constraints on the problem.
A depth-first type search with backtracking is known as a search strategy to enumerate all solutions to a problem. A depth-first type search is one accomplished using a top-down, left-to-right search strategy. As an example, H. S. Stone et al. discuss a backtrack searching technique in an article "Efficient Searching Technique", IBM Technical Disclosure Bulletin, Vol. 30, No. 1, 6/87, pp. 146-148. The Stone et al. article discloses a rule for determining an expansion sequence for a search, wherein an expansion sequence is defined to be a sequence in which abstract objects are examined in a search tree.
It has been found when a sequence of problem instances is solved that the search trees for different problem instances tend to have considerable overlap. However, in a commonly used form of backtrack search, the experience gained in solving one instance of a problem is not used for possible reduction of processing effort in solving other instances of the problem. Thus, with known techniques, no systematic learning takes place. Attempts to improve backtrack search efficiency have generally focused on solving each instance of a problem independently of previous instances of the problem. However, these techniques do not consider optimizing the average efficiency over a sequence of problem instances.
In commonly assigned U.S. Pat. No. 4,752,890, Jun. 21, 1988, "Adaptive Mechanisms for Execution of Sequential Decision", Natarajan and Stone teach that systematic learning of performance parameters during program execution can be used to create adaptive search techniques leading to improved performance in future use of the system. U.S. Pat. No. 4,752,890 furthermore teaches an adaptive search technique that relies on monitoring a performance history of various search alternatives for making decisions on how best to reorder the alternatives so that an average search execution cost is minimized. The class of problems addressed by this U.S. Patent however are not constraint-satisfaction problems where a set of all solutions- is found but are instead problems of the type wherein a single solution is found.
It is thus an object of the invention to provide a method for enhancing the performance of a system that is employed to solve instances of a constraint-satisfaction problem.
It is a further object of the invention to provide methods for optimizing backtrack searching techniques, the method employing a failure history table for recording search-related information for examination during a subsequent search.